/**
 * 使用条件
 * 1、Query Graph 的图编号是从1开始，如1、2、3、4……，而对Source Graph则对编号也不需对应数组编号
 * 2、
 * 
 * 注意：此类已作废！，仅作参考，具体见 MatchGraph类
 */
package com.whu.gmatch;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Set;

import org.jgrapht.graph.SimpleGraph;

import com.whu.graph.util.SequentialIntArray;

public class GraphMatch {

	private static SimpleGraph<LabelVertex, LabelEdge> sourceGraph, queryGraph;
	private LabelVertex []qvertex;
	private LabelVertex [][]cvertex;//匹配节点集合
	private LabelVertex []f;//数组的下标代表 qid,数组内容表示在Source Graph中gid匹配边后对应的那个点
	private int qvertexCount;//query graph 节点个数
	private int[] visited = new int[14];//13个节点，从1开始，数组0位空出

	private static SimpleGraph<LabelVertex, LabelEdge> createSourceGraph() {
		SimpleGraph<LabelVertex, LabelEdge> g = new SimpleGraph<LabelVertex, LabelEdge>(
				LabelEdge.class);

		LabelVertex v1 = new LabelVertex(1, "A");
		LabelVertex v2 = new LabelVertex(2, "B");
		LabelVertex v3 = new LabelVertex(3, "C");
		LabelVertex v4 = new LabelVertex(4, "A");
		LabelVertex v5 = new LabelVertex(5, "B");
		LabelVertex v6 = new LabelVertex(6, "A");
		LabelVertex v7 = new LabelVertex(7, "C");
		LabelVertex v8 = new LabelVertex(8, "A");
		LabelVertex v9 = new LabelVertex(9, "C");
		LabelVertex v10 = new LabelVertex(10, "B");
		LabelVertex v11 = new LabelVertex(11, "A");
		LabelVertex v12 = new LabelVertex(12, "B");
		LabelVertex v13 = new LabelVertex(13, "C");

		// add the vertices
		g.addVertex(v1);
		g.addVertex(v2);
		g.addVertex(v3);
		g.addVertex(v4);
		g.addVertex(v5);
		g.addVertex(v6);
		g.addVertex(v7);
		g.addVertex(v8);
		g.addVertex(v9);
		g.addVertex(v10);
		g.addVertex(v11);
		g.addVertex(v12);
		g.addVertex(v13);

		// add edges to create a circuit
		g.addEdge(v1, v2);
		g.addEdge(v1, v3);
		g.addEdge(v2, v4);
		g.addEdge(v3, v4);
		g.addEdge(v3, v5);
		g.addEdge(v3, v6);
		g.addEdge(v5, v6);
		g.addEdge(v5, v7);
		g.addEdge(v5, v8);
		g.addEdge(v5, v9);
		g.addEdge(v7, v8);
		g.addEdge(v7, v9);
		g.addEdge(v7, v10);
		g.addEdge(v7, v11);
		g.addEdge(v10, v11);
		g.addEdge(v10, v12);
		
		g.addEdge(v3,v13);
		g.addEdge(v5, v13);

		return g;
	}

	private static SimpleGraph<LabelVertex, LabelEdge> createQueryGraph() {
		SimpleGraph<LabelVertex, LabelEdge> g = new SimpleGraph<LabelVertex, LabelEdge>(
				LabelEdge.class);

		LabelVertex v1 = new LabelVertex(1, "A");
		LabelVertex v2 = new LabelVertex(2, "B");
		LabelVertex v3 = new LabelVertex(3, "C");
		LabelVertex v4 = new LabelVertex(4, "C");

		// add the vertices
		g.addVertex(v1);
		g.addVertex(v2);
		g.addVertex(v3);
		g.addVertex(v4);

		// add edges to create a circuit
		g.addEdge(v1, v2);
		g.addEdge(v1, v3);
		g.addEdge(v2, v3);
		g.addEdge(v2, v4);
		g.addEdge(v3, v4);

		return g;
	}

	public void query(SimpleGraph<LabelVertex, LabelEdge> source,
			SimpleGraph<LabelVertex, LabelEdge> query) {
		
		Set<LabelVertex> qset = query.vertexSet();
		qvertexCount = qset.size();
		qvertex = new LabelVertex[qvertexCount+1];//与节点编号一致
		cvertex = new LabelVertex[qvertexCount+1][];//匹配节点编号
		f = new LabelVertex[qvertexCount+1];//map节点编号
		
		int i = 1;
		for(LabelVertex sv :qset){
			qvertex[i++]=sv;
		}
		
		i=1;
		for (LabelVertex qv : query.vertexSet()) {
			String label = qv.getLabel();
			ArrayList<LabelVertex> tmp  = new ArrayList<LabelVertex>();
			for (LabelVertex sv : source.vertexSet()) {
				if (sv.getLabel().equals(label)) {
					tmp.add(sv);
				}
			}
			cvertex[i++]=tmp.toArray(new LabelVertex[tmp.size()]);
		}

		recursiveSearch(qvertex[1]);// query中的第一个节点id,v1
	}

	public void recursiveSearch(LabelVertex qv) {
		int uid,qid=qv.getId();
		LabelVertex uv;
		for(int i=0;i<cvertex[qid].length;i++){
			uv = cvertex[qid][i];
			uid = uv.getId();
			if(visited[uid]==0){//未访问
				if(!matchable(qv, uv)){
					continue;
				}
				
				f[qid]=uv;
				visited[uid]=1;
				if(qid < qvertexCount){
					recursiveSearch(qvertex[qid+1]);
				}else{
					for(int m=1;m<f.length;m++){
						System.out.print("("+f[m].getId()+":"+f[m].getLabel()+")  ");
					}
					System.out.println();
				}
				
				f[qid]=null;
				visited[uid]=0;
			}
		}
	}

	public boolean matchable(LabelVertex qv,LabelVertex uv) {
		int qid = qv.getId();
				
		for(int i=1;i<qid;i++){//只考虑当前节点 和 那些qid之前已经处理过了的节点 之间的边	
			if(queryGraph.containsEdge(qv,qvertex[i])){//查询图包含 qid-->i
				if(!sourceGraph.containsEdge(uv, f[i])){//测试：原图中是否包含 uid-->f(i),以此来判断uid是否是gid在原图中的映射
					return false;
				}
			}
		}
		
		return true;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		sourceGraph = createSourceGraph();
		queryGraph = createQueryGraph();

		GraphMatch gm = new GraphMatch();
		gm.query(sourceGraph, queryGraph);
		
//		MatchGraph mg = new MatchGraph(sourceGraph,queryGraph);
//		if(mg.isMatch()){
//			System.out.println("matched!");
//		}else{
//			System.out.println("unmatched!");
//		}

	}

}
